<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(C卷,200分)- 最小矩阵宽度（Java & JS & Python & C）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>给定一个矩阵&#xff0c;包含 N * M 个整数&#xff0c;和一个包含 K 个整数的数组。</p> 
<p>现在要求在这个矩阵中找一个宽度最小的子矩阵&#xff0c;要求子矩阵包含数组中所有的整数。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>第一行输入两个正整数 N&#xff0c;M&#xff0c;表示矩阵大小。</p> 
<p>接下来 N 行 M 列表示矩阵内容。</p> 
<p>下一行包含一个正整数 K。</p> 
<p>下一行包含 K 个整数&#xff0c;表示所需包含的数组&#xff0c;K 个整数可能存在重复数字。</p> 
<p>所有输入数据小于1000。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>输出包含一个整数&#xff0c;表示满足要求子矩阵的最小宽度&#xff0c;若找不到&#xff0c;输出-1。</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">2 5<br /> 1 2 2 3 1<br /> 2 3 2 3 2<br /> 3<br /> 1 2 3</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">2</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">矩阵第0、3列包含了1&#xff0c;2&#xff0c;3&#xff0c;矩阵第3&#xff0c;4列包含了1&#xff0c;2&#xff0c;3</td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">2 5<br /> 1 2 2 3 1<br /> 1 3 2 3 4<br /> 3<br /> 1 1 4</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">5</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">矩阵第1、2、3、4、5列包含了1、1、4</td></tr></tbody></table> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>本题其实就是“最小覆盖子串”问题的变形。关于最小覆盖子串问题&#xff0c;大家可以先看下&#xff1a;</p> 
<p><a href="https://fcqian.blog.csdn.net/article/details/128092566" rel="nofollow" title="LeetCode - 76 最小覆盖子串_76最小覆盖子串-CSDN博客">LeetCode - 76 最小覆盖子串_76最小覆盖子串-CSDN博客</a></p> 
<p></p> 
<p>当了解了最小覆盖子串问题后&#xff0c;本题中各个关键词可以类比到最小覆盖子串问题中的关键词&#xff1a;</p> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="background-color:#ccff33;text-align:center;">当前题目</td><td style="background-color:#ccff33;text-align:center;">最小覆盖子串问题</td></tr><tr><td>矩阵matrix</td><td>主串s</td></tr><tr><td>矩阵matrix的每一列col列数组</td><td>主串s的每个字符c</td></tr><tr><td>K个元素目标数组nums</td><td>目标串t</td></tr><tr><td>求含有nums数组所有元素的最小宽度子矩阵</td><td>求含有目标串t所有字符的最小覆盖子串</td></tr></tbody></table> 
<p>因此&#xff0c;本题可以使用<span style="color:#fe2c24;"><strong>尺取法</strong></span>高效地求出满足要求地子矩阵地最小宽度。</p> 
<p></p> 
<p>尺取法在上面外链博客中&#xff0c;我做了详细说明&#xff0c;如果还不能够理解地话&#xff0c;可以继续看下这个博客&#xff1a;</p> 
<p><a href="https://blog.csdn.net/qfc_128220/article/details/127418046?ops_request_misc&#61;%257B%2522request%255Fid%2522%253A%2522170464916616800182732891%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&amp;request_id&#61;170464916616800182732891&amp;biz_id&#61;0&amp;utm_medium&#61;distribute.pc_search_result.none-task-blog-2~blog~first_rank_ecpm_v1~rank_v31_ecpm-2-127418046-null-null.nonecase&amp;utm_term&#61;%E6%9C%80%E5%B0%8F%E8%A6%86%E7%9B%96%E5%AD%90%E4%B8%B2&amp;spm&#61;1018.2226.3001.4450" title="华为OD机试 - 关联子串&#xff08;Java &amp; JS &amp; Python &amp; C&#xff09;_华为od算法关联子串-CSDN博客">华为OD机试 - 关联子串&#xff08;Java &amp; JS &amp; Python &amp; C&#xff09;_华为od算法关联子串-CSDN博客</a></p> 
<p></p> 
<p>本题代码已添加详细注释说明&#xff0c;有疑问可以私信我。</p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81" style="background-color:transparent;">JS算法源码</h4> 
<pre><code class="language-javascript">const rl &#61; require(&#34;readline&#34;).createInterface({ input: process.stdin });
var iter &#61; rl[Symbol.asyncIterator]();
const readline &#61; async () &#61;&gt; (await iter.next()).value;

void (async function () {
  // 矩阵 [行数, 列数]
  const [n, m] &#61; (await readline()).split(&#34; &#34;).map(Number);

  // 矩阵
  const matrix &#61; [];
  for (let i &#61; 0; i &lt; n; i&#43;&#43;) {
    matrix.push((await readline()).split(&#34; &#34;).map(Number));
  }

  // 目标数组长度
  const k &#61; parseInt(await readline());

  // 目标数组
  const nums &#61; (await readline()).split(&#34; &#34;).map(Number);

  // cnts[num] 记录的是 目标数组中num元素的个数
  const cnts &#61; new Array(1000).fill(0);
  for (let num of nums) {
    cnts[num]&#43;&#43;;
  }

  // 求解最小子矩阵宽度
  function getResult() {
    // 未完成匹配的元素的个数
    let total &#61; k;

    // 记录最小子矩阵的宽度
    let minLen &#61; Infinity;

    // 当前子矩阵的左边界&#xff08;列号&#xff09;
    let l &#61; 0;
    // 当前子矩阵的右边界&#xff08;列号&#xff09;
    let r &#61; 0;

    // 如果右边界未越界&#xff0c;则可以继续尝试找最小子矩阵
    while (r &lt; m) {
      // 将第r列所有元素纳入子矩阵
      for (let i &#61; 0; i &lt; n; i&#43;&#43;) {
        // 第r列的元素num
        const num &#61; matrix[i][r];

        // cnts[num] 记录的是 目标数组中num元素的个数&#xff0c;也可以理解为&#xff1a;目标数组中num元素剩余未匹配的个数
        // 如果num不是目标数组元素&#xff0c;则cnts[num]初始时必然为0&#xff0c;对于非目标数组元素num, 即使进行了 cnts[num]--&#xff0c; 也不影响总的未匹配数量 total
        // 如果num是目标数组元素&#xff0c;则cnts[num]初始时必然大于0&#xff0c;且随着子矩阵扩大范围&#xff0c;如果子矩阵中包含num元素个数超过了初始cnts[num]数量&#xff0c;则超出部分起不到匹配效果&#xff0c;即不能影响总的未匹配数量
        if (cnts[num]-- &gt; 0) {
          total--;
        }
      }

      // 纳入r列后&#xff0c;看看总的未匹配元素数量total还有几个&#xff0c;如果total为0&#xff0c;则说明当前子矩阵匹配到了所有目标数组元素
      while (total &#61;&#61; 0) {
        // 若此时子矩阵宽度 r - l &#43; 1 更小&#xff0c;则更新最小子矩阵宽度
        minLen &#61; Math.min(minLen, r - l &#43; 1);

        // 由于当前子矩阵已经匹配到所有目标数组元素&#xff0c;因此下一步应该将 l 右移&#xff0c;尝试更小宽度的子矩阵
        for (let i &#61; 0; i &lt; n; i&#43;&#43;) {
          // l 右移&#xff0c;相当于当前子矩阵移除了第 l 列所有元素&#xff0c;被移除的元素num如果是目标数组元素&#xff0c;则对应的未匹配数量应该被恢复
          const num &#61; matrix[i][l];

          // 如果当前num不是目标数组元素&#xff0c;或者当前num是目标数组元素&#xff0c;但是属于超出部分&#xff08;这两种情况必然cnts[num] &lt; 0&#xff09;&#xff0c;则对应num元素的恢复&#xff0c;不能影响到整体未匹配数量total&#xff0c;
          // 如果当前num是目标数组元素&#xff0c;且不是超出部分&#xff08;此时必然cnts[num] &gt;&#61; 0&#xff09;&#xff0c;则对应num元素的恢复&#xff0c;会影响到整体未匹配数量total
          if (cnts[num]&#43;&#43; &gt;&#61; 0) {
            total&#43;&#43;;
          }
        }

        // l右移&#xff0c;且下一轮要继续检查l右移后的子矩阵是否依旧能覆盖目标数组所有元素
        l&#43;&#43;;
      }

      // r右移
      r&#43;&#43;;
    }

    if (minLen &#61;&#61; Infinity) {
      return -1;
    } else {
      return minLen;
    }
  }

  console.log(getResult());
})();
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.Scanner;

public class Main {
  static int n; // 矩阵行数
  static int m; // 矩阵列数
  static int[][] matrix; // 矩阵

  static int k; // 目标数组长度
  static int[] cnts; // cnts[num] 记录的是 目标数组中num元素的个数

  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    n &#61; sc.nextInt();
    m &#61; sc.nextInt();

    matrix &#61; new int[n][m];

    for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
      for (int j &#61; 0; j &lt; m; j&#43;&#43;) {
        matrix[i][j] &#61; sc.nextInt();
      }
    }

    k &#61; sc.nextInt();

    cnts &#61; new int[1000];
    for (int i &#61; 0; i &lt; k; i&#43;&#43;) {
      int num &#61; sc.nextInt();
      cnts[num]&#43;&#43;;
    }

    System.out.println(getResult());
  }

  public static int getResult() {
    // 未完成匹配的元素的个数
    int total &#61; k;

    // 记录最小子矩阵的宽度
    int minLen &#61; Integer.MAX_VALUE;

    // 当前子矩阵的左边界&#xff08;列号&#xff09;
    int l &#61; 0;
    // 当前子矩阵的右边界&#xff08;列号&#xff09;
    int r &#61; 0;

    // 如果右边界未越界&#xff0c;则可以继续尝试找最小子矩阵
    while (r &lt; m) {

      // 将第r列所有元素纳入子矩阵
      for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
        // 第r列的元素num
        int num &#61; matrix[i][r];
        // cnts[num] 记录的是 目标数组中num元素的个数&#xff0c;也可以理解为&#xff1a;目标数组中num元素剩余未匹配的个数
        // 如果num不是目标数组元素&#xff0c;则cnts[num]初始时必然为0&#xff0c;对于非目标数组元素num, 即使进行了 cnts[num]--&#xff0c; 也不影响总的未匹配数量 total
        // 如果num是目标数组元素&#xff0c;则cnts[num]初始时必然大于0&#xff0c;且随着子矩阵扩大范围&#xff0c;如果子矩阵中包含num元素个数超过了初始cnts[num]数量&#xff0c;则超出部分起不到匹配效果&#xff0c;即不能影响总的未匹配数量
        if (cnts[num]-- &gt; 0) {
          total--;
        }
      }

      // 纳入r列后&#xff0c;看看总的未匹配元素数量total还有几个&#xff0c;如果total为0&#xff0c;则说明当前子矩阵匹配到了所有目标数组元素
      while (total &#61;&#61; 0) {
        // 若此时子矩阵宽度 r - l &#43; 1 更小&#xff0c;则更新最小子矩阵宽度
        minLen &#61; Math.min(minLen, r - l &#43; 1);

        // 由于当前子矩阵已经匹配到所有目标数组元素&#xff0c;因此下一步应该将 l 右移&#xff0c;尝试更小宽度的子矩阵
        for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
          // l 右移&#xff0c;相当于当前子矩阵移除了第 l 列所有元素&#xff0c;被移除的元素num如果是目标数组元素&#xff0c;则对应的未匹配数量应该被恢复
          int num &#61; matrix[i][l];

          // 如果当前num不是目标数组元素&#xff0c;或者当前num是目标数组元素&#xff0c;但是属于超出部分&#xff08;这两种情况必然cnts[num] &lt; 0&#xff09;&#xff0c;
          //    则对应num元素的恢复&#xff0c;不能影响到整体未匹配数量total&#xff0c;
          // 如果当前num是目标数组元素&#xff0c;且不是超出部分&#xff08;此时必然cnts[num] &gt;&#61; 0&#xff09;&#xff0c;则对应num元素的恢复&#xff0c;会影响到整体未匹配数量total
          if (cnts[num]&#43;&#43; &gt;&#61; 0) {
            total&#43;&#43;;
          }
        }

        // l右移&#xff0c;且下一轮要继续检查l右移后的子矩阵是否依旧能覆盖目标数组所有元素
        l&#43;&#43;;
      }

      // r右移
      r&#43;&#43;;
    }

    if (minLen &#61;&#61; Integer.MAX_VALUE) {
      return -1;
    } else {
      return minLen;
    }
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python">import sys

# 输入获取
n, m &#61; map(int, input().split())  # 矩阵 [行数, 列数]
matrix &#61; [list(map(int, input().split())) for _ in range(n)]  # 矩阵
k &#61; int(input())  # 目标数组长度
nums &#61; list(map(int, input().split()))  # 目标数组

# cnts[num] 记录的是 目标数组中num元素的个数
cnts &#61; [0] * 1000
for num in nums:
    cnts[num] &#43;&#61; 1


# 算法入口
def getResult():
    # 未完成匹配的元素的个数
    total &#61; k

    # 记录最小子矩阵的宽度
    minLen &#61; sys.maxsize

    l &#61; 0  # 当前子矩阵的左边界&#xff08;列号&#xff09;
    r &#61; 0  # 当前子矩阵的右边界&#xff08;列号&#xff09;

    # 如果右边界未越界&#xff0c;则可以继续尝试找最小子矩阵
    while r &lt; m:
        # 将第r列所有元素纳入子矩阵
        for i in range(n):
            #  第r列的元素numR
            numR &#61; matrix[i][r]

            # cnts[numR] 记录的是 目标数组中numR元素的个数&#xff0c;也可以理解为&#xff1a;目标数组中numR元素剩余未匹配的个数
            # 如果numR不是目标数组元素&#xff0c;则cnts[numR]初始时必然为0&#xff0c;对于非目标数组元素numR, 即使进行了 cnts[numR]--&#xff0c; 也不影响总的未匹配数量 total
            # 如果numR是目标数组元素&#xff0c;则cnts[numR]初始时必然大于0&#xff0c;且随着子矩阵扩大范围&#xff0c;如果子矩阵中包含numR元素个数超过了初始cnts[numR]数量&#xff0c;则超出部分起不到匹配效果&#xff0c;即不能影响总的未匹配数量
            if cnts[numR] &gt; 0:
                total -&#61; 1
            cnts[numR] -&#61; 1

        # 纳入r列后&#xff0c;看看总的未匹配元素数量total还有几个&#xff0c;如果total为0&#xff0c;则说明当前子矩阵匹配到了所有目标数组元素
        while total &#61;&#61; 0:
            # 若此时子矩阵宽度 r - l &#43; 1 更小&#xff0c;则更新最小子矩阵宽度
            minLen &#61; min(minLen, r - l &#43; 1)

            # 由于当前子矩阵已经匹配到所有目标数组元素&#xff0c;因此下一步应该将 l 右移&#xff0c;尝试更小宽度的子矩阵
            for i in range(n):
                # l 右移&#xff0c;相当于当前子矩阵移除了第 l 列所有元素&#xff0c;被移除的元素numL如果是目标数组元素&#xff0c;则对应的未匹配数量应该被恢复
                numL &#61; matrix[i][l]

                # 如果当前numL不是目标数组元素&#xff0c;或者当前numL是目标数组元素&#xff0c;但是属于超出部分&#xff08;这两种情况必然cnts[numL] &lt; 0&#xff09;&#xff0c;则对应numL元素的恢复&#xff0c;不能影响到整体未匹配数量total&#xff0c;
                # 如果当前numL是目标数组元素&#xff0c;且不是超出部分&#xff08;此时必然cnts[numL] &gt;&#61; 0&#xff09;&#xff0c;则对应numL元素的恢复&#xff0c;会影响到整体未匹配数量total
                if cnts[numL] &gt;&#61; 0:
                    total &#43;&#61; 1
                cnts[numL] &#43;&#61; 1

            # l右移&#xff0c;且下一轮要继续检查l右移后的子矩阵是否依旧能覆盖目标数组所有元素
            l &#43;&#61; 1

        # r右移
        r &#43;&#61; 1

    if minLen &#61;&#61; sys.maxsize:
        return -1
    else:
        return minLen


# 算法调用
print(getResult())
</code></pre> 
<p></p> 
<h4>C算法源码</h4> 
<pre><code class="language-cpp">#include &lt;stdio.h&gt;
#include &lt;limits.h&gt;
#include &lt;math.h&gt;

#define MAX_SIZE 1000

// 矩阵行数, 矩阵列数
int n, m;
// 矩阵
int matrix[MAX_SIZE][MAX_SIZE];

// 目标数组长度
int k;
// cnts[num] 记录的是 目标数组中num元素的个数
int cnts[MAX_SIZE] &#61; {0};

int getResult() {
    // 未完成匹配的元素的个数
    int total &#61; k;

    // 记录最小子矩阵的宽度
    int minLen &#61; INT_MAX;

    // 当前子矩阵的左边界&#xff08;列号&#xff09;
    int l &#61; 0;
    // 当前子矩阵的右边界&#xff08;列号&#xff09;
    int r &#61; 0;

    // 如果右边界未越界&#xff0c;则可以继续尝试找最小子矩阵
    while (r &lt; m) {
        // 将第r列所有元素纳入子矩阵
        for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
            // 第r列的元素num
            int num &#61; matrix[i][r];

            // cnts[num] 记录的是 目标数组中num元素的个数&#xff0c;也可以理解为&#xff1a;目标数组中num元素剩余未匹配的个数
            // 如果num不是目标数组元素&#xff0c;则cnts[num]初始时必然为0&#xff0c;对于非目标数组元素num, 即使进行了 cnts[num]--&#xff0c; 也不影响总的未匹配数量 total
            // 如果num是目标数组元素&#xff0c;则cnts[num]初始时必然大于0&#xff0c;且随着子矩阵扩大范围&#xff0c;如果子矩阵中包含num元素个数超过了初始cnts[num]数量&#xff0c;则超出部分起不到匹配效果&#xff0c;即不能影响总的未匹配数量
            if (cnts[num]-- &gt; 0) {
                total--;
            }
        }

        // 纳入r列后&#xff0c;看看总的未匹配元素数量total还有几个&#xff0c;如果total为0&#xff0c;则说明当前子矩阵匹配到了所有目标数组元素
        while (total &#61;&#61; 0) {
            // 若此时子矩阵宽度 r - l &#43; 1 更小&#xff0c;则更新最小子矩阵宽度
            minLen &#61; (int) fmin(minLen, r - l &#43; 1);

            // 由于当前子矩阵已经匹配到所有目标数组元素&#xff0c;因此下一步应该将 l 右移&#xff0c;尝试更小宽度的子矩阵
            for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
                // l 右移&#xff0c;相当于当前子矩阵移除了第 l 列所有元素&#xff0c;被移除的元素num如果是目标数组元素&#xff0c;则对应的未匹配数量应该被恢复
                int num &#61; matrix[i][l];

                // 如果当前num不是目标数组元素&#xff0c;或者当前num是目标数组元素&#xff0c;但是属于超出部分&#xff08;这两种情况必然cnts[num] &lt; 0&#xff09;&#xff0c;
                //    则对应num元素的恢复&#xff0c;不能影响到整体未匹配数量total&#xff0c;
                // 如果当前num是目标数组元素&#xff0c;且不是超出部分&#xff08;此时必然cnts[num] &gt;&#61; 0&#xff09;&#xff0c;则对应num元素的恢复&#xff0c;会影响到整体未匹配数量total
                if (cnts[num]&#43;&#43; &gt;&#61; 0) {
                    total&#43;&#43;;
                }
            }

            // l右移&#xff0c;且下一轮要继续检查l右移后的子矩阵是否依旧能覆盖目标数组所有元素
            l&#43;&#43;;
        }

        // r右移
        r&#43;&#43;;
    }

    if (minLen &#61;&#61; INT_MAX) {
        return -1;
    } else {
        return minLen;
    }
}

int main() {
    scanf(&#34;%d %d&#34;, &amp;n, &amp;m);

    for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
        for (int j &#61; 0; j &lt; m; j&#43;&#43;) {
            scanf(&#34;%d&#34;, &amp;matrix[i][j]);
        }
    }

    scanf(&#34;%d&#34;, &amp;k);

    for (int i &#61; 0; i &lt; k; i&#43;&#43;) {
        int num;
        scanf(&#34;%d&#34;, &amp;num);
        cnts[num]&#43;&#43;;
    }

    printf(&#34;%d\n&#34;, getResult());

    return 0;
}</code></pre> 
<p></p>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>